package cn.leonis.leetcode;

import java.util.*;

/**
 * @Author Tobi
 * @Date 2021-07-12 上午12:33
 * 求两个数组的交集2
 */
public class IntersectionTwoArraySolution {

    public static void main(String[] args) {
        int[] nums2 = new int[]{1, 2, 1};
        int[] nums1 = new int[]{2, 2};
        IntersectionTwoArraySolution solution = new IntersectionTwoArraySolution();
        int[] intersect = solution.intersect(nums1, nums2);
        for (int i = 0; i < intersect.length; i++) {
            System.out.println(intersect[i]);
        }
    }

    /**
     * 这种方式有缺陷，因为如果长度短的数组又出现重复的，但是在长数组中只出现了一次，还是会出现两次
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();

        List<Integer> result = new ArrayList<>();

        if (nums1.length > nums2.length) {
            for (int i = 0; i < nums2.length; i++) {
                list.add(nums2[i]);
            }
            for (int i = 0; i < nums1.length; i++) {
                if (list.contains(nums1[i])) {
                    list.remove(list.lastIndexOf(nums1[i]));
                    result.add(nums1[i]);
                }
            }
        } else {
            return intersect(nums2, nums1);
        }

        Object[] objects = result.toArray();
        int[] res = new int[objects.length];
        for (int i = 0; i < objects.length; i++) {
            res[i] = (int)objects[i];
        }
        return res;
    }

    /**
     * 使用HashMap来记录次数，当次数-到0时，将不再添加，判断短的就可以，因此相交需要最小的也包含
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect1(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect1(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums1) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int[] intersect = new int[nums2.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersect[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                }else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersect, 0, index);
    }
}
